Warp wrote:
>   This does not perform a true depth-first search, but it doesn't matter
> because it makes the job with the minimum amount of stack usage (ie. a
> triangle is never pushed onto the stack more than once).
>   Of course it requires that the mesh is connected.

I'm sorry, because I didn't write precisely which variant of 
"depth-first-search" I meant. What you described is exactly what 
I had in mind.

> By the way, for the algorithm to work fast, you need to know for a 
triangle
> which three triangles are adjacent to it. This is a separate problem in
> itself.
>  For this we need to introduce the notion of "edge". That is, an "edge"
> knows the two triangles sharing that edge, and each triangle should know
> the three edges it uses.
>  Initializing the edge information fast is a problem in itself.

I agree with you, that this is the bigger problem in terms of running time.
The vertices already have a unique number. (Probably, it's a good idea
to make sure that the numbers are unique first.)
What I suggest is to represent every edge by the sorted numbers of its
vertices and a pointer to its triangle. Sorting these pairs 
lexicographically should reveal triangles that share an edge. It's then 
possible to store pointers to the three neighbors for each triangle. 
However, this dominates the overall algorithm, because sorting needs 
O(n log n) time.

Best regards
Thomas

Post a reply to this message